// https://leetcode.cn/problems/di-string-match/description/

// 算法思路总结：
// 1. 使用双指针策略匹配升降序列要求
// 2. 遇到'I'选择当前最小可用数字保证上升
// 3. 遇到'D'选择当前最大可用数字保证下降
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    vector<int> diStringMatch(string s) 
    {
        int m = s.size();
        int l = 0, r = m;

        vector<int> ret;
        for (const char& ch : s)
        {
            if (ch == 'I')
                ret.push_back(l++);
            else 
                ret.push_back(r--);
        }
        ret.push_back(r);

        return ret;
    }
};

int main()
{
    string s1 = "IDID", s2 = "III";
    Solution sol;

    auto r1 = sol.diStringMatch(s1);
    auto r2 = sol.diStringMatch(s2);

    for (const int& num : r1)
        cout << num << " ";
    cout << endl;

    for (const int& num : r2)
        cout << num << " ";
    cout << endl;

    return 0;
}